package site.wanjiahao.union;

import java.util.Arrays;

/**
 * Quick Union
 * find O(logn)
 * Union O(logn)
 *
 * 基于size的优化可能控制起来不是那么稳定，所以需要基于rank的优化
 */
public class UnionFind_QU_R extends UnionFind_QU{

    int[] ranks;

    public UnionFind_QU_R(int capacity) {
        super(capacity);
        ranks = new int[capacity];
        // 每个节点的size都为1
        Arrays.fill(ranks, 1);
    }

    @Override
    public void union(int v1, int v2) {
       // 将v1元素的父元素置为
        int p1 = find(v1);
        int p2 = find(v2);
        // 两父元素相等，不用进行任何操作
        if (p1 == p2) return;
        // 将元素数量少的一方，嫁接到元素数量多的一方上
        if (ranks[p1] > ranks[p2]) {
            parents[p2] = p1;
        } else if(ranks[p1] < ranks[p2]) {
            parents[p1] = p2;
        } else {
            // 相等，左偏向右
            parents[p1] = p2;
            // 增加rank值
            ranks[p2]++;
        }
    }
}
